import functools

class Solution(object):
    def maxCoins(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        nums.insert(0, 1)
        nums.append(1)
        @functools.cache
        def search(i, j):
            if j - i == 1:
                return 0
            else:
                if j - i == 2:
                    return nums[i] * nums[i + 1] * nums[i + 2]
                else:
                    max_value = 0
                    for k in range(i + 1, j):
                        max_value = max(max_value, nums[k] * nums[i] * nums[j] + search(i, k) + search(k, j))
                    return max_value

        return search(0, len(nums) - 1)


data = Solution()
nums = [3, 1, 5, 8, 10, 5, 7, 6, 1, 2, 4, 10]
print(data.maxCoins(nums))
nums = [1, 5]
print(data.maxCoins(nums))
